/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 //解法一：暴力转换法。不推荐。一旦数据大了比较难以计算。
class Solution {
    //本题必须非常注意到int的最大表示范围问题！！，java里面int最多表示10位数。所以必须用long
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        long result = convertListToInteger(l1) + convertListToInteger(l2);
        return convertIntegerToList(result);

    }

    //进去是 2，4，3 这样的链表，吐出来是int 342
    private long convertListToInteger(ListNode root){
        //个十百……以此类推
        long returnNum = 0;
        long digit = 1;
        while(root != null){
            returnNum = returnNum + root.val * digit;
            root = root.next;
            digit *= 10;
        }
        return returnNum;
    }

    //进去是 int 342 , 吐出来的是 2,4,3 这样的链表
    private ListNode convertIntegerToList(long num){
        //边界检查：num只有个位数
        if (num/10 == 0){
            return new ListNode((int) num);
        }
        ListNode root = new ListNode((int) (num % 10));  //取根节点
        ListNode workNode = root;   //工作指针
        num = num / 10;

        while (num != 0){
            workNode.next = new ListNode((int) (num % 10));  //取个位
            workNode = workNode.next;
            num = num / 10;
        }

        return root;
    }
}

//解法2：双指针相加，强烈推荐！
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode headNode = new ListNode(); //申明一个空的头结点
        ListNode workNode = headNode;   //工作指针
        int digit = 0;  //进位
        int l1Val, l2Val = 0;   //如果l1或l2结点为空，将其值填充为0
        while (l1 != null || l2 != null) {  //当l1和l2全部为空，就停止循环
            if (l1 == null) {
                l1Val = 0;
            } else {
                l1Val = l1.val;
            }
            if (l2 == null) {
                l2Val = 0;
            } else {
                l2Val = l2.val;
            }

            int sum = l1Val + l2Val + digit;
            if (sum >= 10) {  //和大于10进位就+1
                sum = sum % 10;   //骟掉十位
                if (digit == 0) {
                    digit = 1;        //进位
                }
            } else {
                if (digit > 0) {
                    digit = 0;      //不进位
                }
            }
            workNode.next = new ListNode(sum);
            workNode = workNode.next;
            //l1和l2步进
            if (l1!=null){
                l1 = l1.next;
            }
            if (l2 != null){
                l2 = l2.next;
            }
        }
        if (digit == 1){
            workNode.next = new ListNode(1);
        }
        return headNode.next;
    }
}